模拟赛题解/2025.10.5 模拟赛

T1-诋毁原神（slander）

题面

在提瓦特大陆上存在着 $m$ 种元素，刚刚来到这片大陆的旅行者对第 $i$ 种元素掌控力 $p_i = 0$。

但是这样的成长速度还是太慢了，因此旅行者为了快速提升自己各种元素掌控力接受了 $n$ 场测试。

具体的，每一场测试 $i$ 都会考核所有 $m$ 种元素掌控力，若此时旅行者对于所有元素 $j$ 的掌控力 $p_j$ 均 $\ge w_{i,j}$，那么旅行者将通过这场考验，并且第 $j$ 种元素掌控力将提升 $v_{i,j}$，即将 $p_j$ 加上 $v_{i,j}$。

旅行者可以以任意顺序参加测试，但每一场测试只能参加一次。同时，她希望尽可能多的提升自己的实力，请你帮助她计算出最多能通过的测试数量。

$1 \le n \le 5\times 10^4$，$n-1 \le m \le 10^5$，$-1 \le d_i < n$。

题解

考虑一个显然的贪心：每次选择所有能通过的测试中，提升向量 $v$ 的“综合提升”最大的那一个。

然而这在多维情况下未必正确。

可以将这个问题看作多维偏序：每个测试 $i$ 有要求向量 $w_i$，收益向量 $v_i$。

若旅行者当前掌控力向量为 $p$，则可以选择所有满足 $w_i \le p$（按分量）的测试，并使 $p \gets p+v_i$。

这其实是一个「多维可达性问题」，但维数可能较大。

注意到 $n \times m \le 10^6$，可在所有测试之间建立依赖关系图：

若 $w_i \le w_j-v_j$，则 $i$ 需要在 $j$ 之前完成。这样得到一个 DAG。

于是问题转化为： 求该 DAG 的最长路径长度。

复杂度 $O(nm)$ 建边后 $O(n+m)$ 拓扑 DP 即可。

T2-理解原神（realize）

题面

在提瓦特大陆上有 $n$ 个城市，这些城市由 $m$ 条长度为 $1$ 的无向道路相连，并且可以从任何一个城市走到任何另一个城市。

旅行者在这 $n$ 个城市中选择了一个城市进行休息，然后规划接下来的行程。为了方便，她记录下了各个城市 $i$ 到她选择休息的城市的最短路长度，记作 $d_i$。

可是她已经忘记了某一些 $d_i$，也可能记错一些 $d_i$，也忘记了她选择休息的城市，请你帮助旅行者确定她选择的城市可能是哪些。

$1 \le n \le 5\times 10^4$，$n-1 \le m \le 10^5$，$-1 \le d_i < n$，并且保证图没有重边自环。

题解

我们要判断哪些点 $x$ 可以作为起点，使得与已知 $d_i$ 一致。

一个朴素想法是：枚举 $x$，从 $x$ BFS 得到最短路，与给定的 $d$ 对比。

显然复杂度 $O(n(n+m))$ 不可行。

可以反过来思考：

若某个点 $u$ 被确定距离为 $d_u$，则所有相邻点 $v$ 必然满足 $|d_v-d_u|=1$。

若某个 $d_i=-1$，则它对结果没有约束。

我们可以把所有有已知 $d_i$ 的点作为锚点，检查其相邻点的约束是否矛盾。

更高效的方法：

以所有 $d_i=0$ 的点为可能的根，从这些点 BFS；

若能得到一个与已知 $d_i$ 一致的距离分配，则该根可行。

由于每次 BFS 复杂度 $O(n+m)$，而起点数量可能较多，

可以预处理一遍全局距离：对所有已知 $d_i$ 建立一个「多源 BFS」即可同时验证所有可能的根。

整体复杂度 $O(n+m)$。

T3-追随原神（follow）

题面

旅行者正在为其他冒险者设计一个秘境！

旅行者决定在一棵由 $n$ 个节点、$n-1$ 条边构成的树上建造这个秘境，1 号节点为这棵树的根节点。定义 $p_i$ 表示 $i$ 节点的父亲节点，每条边 $(p_u, u)$ 上都标有符号 $<$ 和 $>$。

她有 $n$ 个宝箱，价值分别为 $1 \sim n$，她希望将这些宝箱放置在每一个节点，记节点 $i$ 上放置宝箱的价值为 $a_i$，则需要满足：

• 对于标有 $<$ 的边 $(p_u,u)$，需满足 $a_{p_u} < a_u$。
• 对于标有 $>$ 的边 $(p_u,u)$，需满足 $a_{p_u} > a_u$。

请你帮助旅行者计算她有多少种放置宝箱的方案数，这个结果可能很大，只需输出对 $10^9+7$ 取模的结果。

$1 \le n \le 3000$，并且 $\forall i\in[2,n]$ 有 $1\le p_i < i$。

题解

考虑一棵树，每条边 $(p_u,u)$ 带有方向约束：

若为 $<$，则 $a_{p_u} < a_u$；

若为 $>$，则 $a_{p_u} > a_u$。

我们要计算所有合法赋值 $a_1,\dots,a_n$ 为 $1\sim n$ 的排列的数量。

显然这是一个偏序计数问题。

树形偏序的拓扑序数量可通过 DP 求得。

设 $f_u(k)$ 表示在子树 $u$ 内有 $k$ 个元素时的方案数。

子节点之间根据符号$<$ 或 $>$ 决定合并时的排列组合数。

合并两子树的转移可用组合数：

$$f_u(s+t) = \sum_{i=0}^{s+t} f_u(i)\, f_v(s+t-i)\, \binom{s+t}{i}.$$

由于 $n \le 3000$，可用树形 DP + 前缀卷积实现，复杂度 $O(n^2)$。

实现上先对所有子树求大小和 $f_v$，然后自底向上合并。

最终答案为 $f_{\text{root}}(n)$ 对 $10^9+7$ 取模。

T4-成为原神（become）

题面

在提瓦特大陆上，有 $n$ 个城市，它们由 $m$ 条可以相互到达的道路连接起来，为了交通的便利，每一个城市都能通过若干条道路到达任意其它城市。

旅行者对于一条道路是否有挑战有着独特的看法，她为每一条道路 $i$ 设置了一个评分 $w_i$，同时她认为一条路径的难度为路径上经过道路的最大评分与最小评分之和。旅行者现在在城市 1，为了确定下一步的行程，希望你能帮助她对于每一个城市 $u>1$ 计算出所有 $1\overset{\text{简单路径}}{\longrightarrow} u$（不重复经过同一条道路）的路径难度的最小值。

$2\le n \le 3\times 10^5$，$1\le m \le 3\times 10^5$，对于每一条道路 $(u_i,v_i,w_i)$ 都有 $1\le u_i,v_i\le n$，$0\le w_i \le 10^9$。

题解

对于 Subtask 2，本质是确定了最小值，要使 $1 \leadsto u$ 路径上边权取最大值最小，显然直接上 Kruskal 重构树。

对于 Subtask 3，本质是确定了最大值，要使 $1 \leadsto u$ 路径上边权取最小值最大，显然直接跑边双即可。

这启发我们考虑枚举一条边，让它成为最大值/最小值，容易发现枚举最大值是更有前途的。

将所有边按边权从小到大排序，依次枚举一条边，这条边就是当前的最大值，现在可能经过这条边之前的边。

同时注意到一条边如果在 $1 \leadsto u$ 的路径上，那么也一定在缩完边双后的 $1 \leadsto u$ 的路径上。那么考虑加入一条连接 $(u, v)$ 的边带来的影响：

• 若 $u, v$ 已经在一个边双里面了，则没有任何影响，因为这条边一定比已经在边双中的所有边都大。
• 若 $u, v$ 已经在同一棵树，但不在同一个边双内，则需要把 $u \leadsto v$ 路径上所有点缩起来，这个点的点权是路径上所有点权和边权的最小值，然后更新子树内所有点的答案。
• 若 $u, v$ 不在同一个连通块内，直接把 $u, v$ 连起来即可。

直接暴力处理这三种情况，复杂度是 $O(n^2)$ 的，考虑优化。

注意到第三种情况边一定是最小生成树上的边，于是先跑出整个图的最小生成树，预处理到每一个点的点权。

现在的问题是，某个点可能在还未与 $1$ 连通的时候就记录了答案，因此我们需要在每个点与 $1$ 所在连通块连接时，重新计算这个点的答案。

用两棵线段树，分别维护树上路径的最小值和实际的答案，需要支持区间 check min，单点修改和单点查询。

对于第二种情况的缩点操作可以用并查集维护，让并查集的树为连通块深度最小的点即可，复杂度是均摊的，总复杂度 $O((n + m)\log n)$。